package random;

import java.util.HashMap;
import java.util.Map;

/**
 * 大餐计数
 *
 * 大餐 是指 恰好包含两道不同餐品 的一餐，其美味程度之和等于 2 的幂。
 * 你可以搭配 任意 两道餐品做一顿大餐。
 * 给你一个整数数组 deliciousness ，其中 deliciousness[i] 是第 i 道餐品的美味程度，返回你可以用数组中的餐品做出的不同 大餐 的数量。结果需要对 10^9 + 7 取余。
 * 注意，只要餐品下标不同，就可以认为是不同的餐品，即便它们的美味程度相同。
 */

public class L1711 {

    public static void main(String[] args) {

        System.out.println(new L1711().countPairs(new int[]{2160,1936,3,29,27,5,2503,1593,2,0,16,0,3860,28908,6,2,15,49,6246,1946,23,105,7996,196,0,2,55,457,5,3,924,7268,16,48,4,0,12,116,2628,1468}));
    }

    // 超过时间限制（暴力解法，就是遍历每两个都算一次和，然后判断这个是否为2的次幂）
    public int countPairs(int[] deliciousness) {

        int count = 0;
        for (int i = 0; i < deliciousness.length - 1; i++) {

            for (int j = i + 1; j < deliciousness.length; j++) {

                int num = deliciousness[i] + deliciousness[j];
                if (num == 0) continue;
                // 判断该数是否为 2 的次幂
                if ((num & num -1) == 0) {
                    count++;
                }

            }

        }
        return count;
    }


    /**
     * 使用哈希进行调整，使复杂度减低到 nlog
     *
     * 使用哈希表存储数组中的每个元素的出现次数，遍历到数组 deliciousness 中的某个元素时，
     * 在哈希表中寻找与当前元素的和等于 2 的幂的元素个数，然后用当前元素更新哈希表。由于遍历数组时，
     * 哈希表中已有的元素的下标一定小于当前元素的下标，因此任意一对元素之和等于 2 的幂的元素都不会被重复计算。
     *
     * @param deliciousness
     * @return
     */
    public int countPairs2(int[] deliciousness) {
        final int MOD = 1000000007;
        int maxVal = 0;
        for (int val : deliciousness) {
            maxVal = Math.max(maxVal, val);
        }
        int maxSum = maxVal * 2;        // 最大的和不超过最大数的两倍
        int pairs = 0;                  // 数量
        Map<Integer, Integer> map = new HashMap<>();
        int n = deliciousness.length;
        for (int i = 0; i < n; i++) {
            int val = deliciousness[i];
            for (int sum = 1; sum <= maxSum; sum <<= 1) {
                int count = map.getOrDefault(sum - val, 0);     // 获取该值对应的能组成2次幂的数是否存在
                pairs = (pairs + count) % MOD;
            }
            map.put(val, map.getOrDefault(val, 0) + 1);     // 储存该值存在的数量
        }
        return pairs;
    }

    /*作者：LeetCode-Solution
    链接：https://leetcode-cn.com/problems/count-good-meals/solution/da-can-ji-shu-by-leetcode-solution-fvg9/
    来源：力扣（LeetCode）
    著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。*/
}
